package leetcode;

import java.util.ArrayList;
import java.util.Collections;

public class IsSubsequence {

	public static void main(String[] args) {
		IsSubsequence object = new IsSubsequence();
		String string = "leeeeetcode";
		String t = "leetcode";
//		String t = "yyyyylyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy" +
//				"yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy" +
//				"yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy" +
//				"yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyeyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy" +
//				"yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy" +
//				"yyyyyyyyyyyyyeyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy" +
//				"yyyyyyyyyyyyyyyyyyyyyeyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy" +
//				"yyyyyyyyyyyyyyyyyyyyyyyyyyytyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy" +
//				"yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyycyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy" +
//				"yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyoyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy" +
//				"yyyyyyyyyyyyyyyyyyyyyyydyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy" +
//				"yyyyyyyyyeyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy" +
//				"yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy";
		System.out.println(object.isSubsequence(string, t));
	}
	
	// 判断s是否是t的子序列
	public boolean isSubsequence(String s, String t) {
		if (s == null || t == null) {
			return true;
		}
		int length1 = s.length();
		int length2 = t.length();
		if (length1 <= 0 || length2 <= 0) {
			return length1 == 0;
		}
		if (length1 > length2) {
			return false;
		}
		char[] sChas = s.toCharArray();
		char[] tChas = t.toCharArray();
//		boolean[][] dp = new boolean[tChas.length][sChas.length];
//		dp[0][0] = tChas[0] == sChas[0];
//		for (int i = 1; i < tChas.length; i++) {
//			dp[i][0] = dp[i - 1][0] || (tChas[i] == sChas[0]);
//		}
//		for (int i = 1; i < tChas.length; i++) {
//			for (int j = 1; j < sChas.length; j++) {
//				if (tChas[i] == sChas[j]) {
//					dp[i][j] = dp[i - 1][j - 1];
//				} else {
//					dp[i][j] = dp[i - 1][j];
//				}
//			}
//		}
		
//		boolean[] dp = new boolean[sChas.length];
//		dp[0] = tChas[0] == sChas[0];
//		for (int i = 1; i < tChas.length; i++) {
//			dp[i][0] = dp[i - 1][0] || (tChas[i] == sChas[0]);
//		}
		
		//dp的解法竟然不对
		//而且时间复杂度太高
		boolean[] dp = new boolean[sChas.length];
		dp[0] = tChas[0] == sChas[0];
		for (int i = 1; i < tChas.length; i++) {
//			终于知道为什么不对了，因为又是从小往大的，之前在哪个题里面遇到过
//			优化的时候，因为dp[j]可能会用带dp[j - 1]的值，所以如果从小往大会导致后面的数据不对
//			应该从右往左
//			for (int j = 0; j < sChas.length; j++) {
			for (int j = sChas.length - 1; j >= 0; j--) {
				if(j > i){
					break;
				}
				if(j == 0){
					dp[j] = dp[j] || (tChas[i] == sChas[0]);
					continue;
				}
				if (tChas[i] == sChas[j]) {
					dp[j] = dp[j - 1];
				} 
			}
		}
		return dp[sChas.length - 1];
	}
	
	//使用双指针
	public boolean isSubsequence2(String s, String t) {
		if (s == null || t == null) {
			return true;
		}
		int length1 = s.length();
		int length2 = t.length();
		if (length1 <= 0 || length2 <= 0) {
			return length1 == 0;
		}
		if (length1 > length2) {
			return false;
		}
		char[] sChas = s.toCharArray();
		char[] tChas = t.toCharArray();
		
		int sIndex = 0;
		int tIndex = 0;
		int count = 0;
		for(; tIndex < tChas.length; tIndex++){
			if(tChas[tIndex] == sChas[sIndex]){
				sIndex++;
				count++;
			}
			if(count == length1){
				return true;
			}
		}
		return false;
	}
	
	//binary search
	public boolean isSubsequence3(String s, String t) {
		if (s == null || t == null) {
			return true;
		}
		//there are only lower case letter
		//用来存储每个字符出现的下标位置
		ArrayList<Integer>[] lists = new ArrayList[26];
		int sLength = s.length();
		int tLength = t.length();
		for(int i = 0; i < tLength; i++){
			if(lists[t.charAt(i) - 'a'] == null){
				lists[i] = new ArrayList<>();
			}
			lists[t.charAt(i) - 'a'].add(i);
		}
		
		//记录上次找到与s对应字母相等时候的下标的后一个下标
		int pre = 0;
		for (int i = 0; i < sLength; i++) {
			int index = Collections.binarySearch(lists[s.charAt(i) - 'a'], pre);
			//index此时表示大于pre的下标所处位置
			if(index < 0){
				index = -index - 1;
			}
			if(index >= tLength){
				return false;
			}
			//因为lists[s.charAt(i) - 'a'].get(index)此时匹配的是s.charAt(i)，假设是'm'
			//如果下一个字符也是'm'，但不能重复匹配，所以需要加1
			pre = lists[s.charAt(i) - 'a'].get(index) + 1;
		}
		return true;
	}
}
